package com.shm.leetcode;

import java.util.Arrays;
import java.util.Stack;

/**
 *
 * @author SHM5500. 乘积为正数的最长子数组长度  显示英文描述
 * 通过的用户数 761
 * 尝试过的用户数 1243
 * 用户总通过次数 766
 * 用户总提交次数 2274
 * 题目难度 Medium
 * 给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
 *
 * 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
 *
 * 请你返回乘积为正数的最长子数组长度。
 *
 *
 *
 * 示例  1：
 *
 * 输入：nums = [1,-2,-3,4]
 * 输出：4
 * 解释：数组本身乘积就是正数，值为 24 。
 * 示例 2：
 *
 * 输入：nums = [0,1,-2,-3,-4]
 * 输出：3
 * 解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
 * 注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
 * 示例 3：
 *
 * 输入：nums = [-1,-2,-3,0,1]
 * 输出：2
 * 解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
 * 示例 4：
 *
 * 输入：nums = [-1,2]
 * 输出：1
 * 示例 5：
 *
 * 输入：nums = [1,2,3,5,-6,4,0,10]
 * 输出：4
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 */
public class GetMaxLen {
    public int getMaxLen(int[] nums) {
        int total = 1;
        for (int num : nums) {
            if (num>0){
                total*=1;
            }else if (num==0){
                total*=0;
            }else {
                total*=(-1);
            }
        }
        if (total>0){
            return nums.length;
        }else if (total==0){
            //超出内存限制
            for (int i=0,j=nums.length-1;i<=j;i++,j--){
                if (nums[i] == 0){
//                    return nums.length-(i+1);
                    return Math.max(getMaxLen(Arrays.copyOfRange(nums,0,i)),getMaxLen(Arrays.copyOfRange(nums,i+1,nums.length)));
                }
                if (nums[j] == 0){
                    return Math.max(getMaxLen(Arrays.copyOfRange(nums,0,j)),getMaxLen(Arrays.copyOfRange(nums,j+1,nums.length)));
                }
            }
        }else {
            for (int i=0,j=nums.length-1;i<=j;i++,j--){
                if (nums[i] < 0){
                    return nums.length-(i+1);
                }
                if (nums[j] < 0){
                    return j;
                }
            }
        }
        return 0;
    }


    /**
     * 思路就是申请一个数组，拷贝原数组，但是不同的是，遇到正数设置为1，负数设置为-1，防止后续相乘会溢出。
     * 如果我们把数组用0切割，那么一个个小数组中就都是非0的数字，答案一定在其中，比如[a, b, c, d, e, f]
     * 可能成为答案的数组有很多个，需要证明在以a为开头的子数组，或者以f为结尾的子数组中，求一个共同答案，就是这个子数组能得到的最大长度。那么遍历一遍辅助数组，不是0就压栈，遇到0就去弹出栈，求可能的答案，注意弹出的时候压入另外一个栈，再把另外一个栈弹出求一个答案，这样就相当于求得了以a开头的答案和以f为结尾的答案。
     *
     * 作者：durable
     * 链接：https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product/solution/shen-qing-2ge-zhan-onshi-jian-by-durable/
     * @param nums
     * @return
     */
    public int getMaxLen_2(int[] nums) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> stack1 = new Stack<>();
        int[] help = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                help[i] = 1;
            }
            if(nums[i] < 0) {
                help[i] = -1;
            }
        }
        int res = 1;
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            if(help[i] == 1) {
                stack.push(help[i]);
            }else if(help[i] == -1) {
                stack.push(help[i]);
            }else{
                res = 1;
                count = 0;
                while(!stack.isEmpty()) {
                    count++;
                    int a = stack.pop();
                    res = res * a;
                    if(res == 1) {
                        ans = Math.max(ans, count);
                    }
                    stack1.push(a);
                }
                res = 1;
                count = 0;
                while(!stack1.isEmpty()) {
                    count++;
                    int a = stack1.pop();
                    res = res * a;
                    if(res == 1) {
                        ans = Math.max(ans, count);
                    }
                }
            }
        }
        res = 1;
        count = 0;
        while(!stack.isEmpty()) {
            count++;
            int a = stack.pop();
            res = res * a;
            if(res == 1) {
                ans = Math.max(ans, count);
            }
            stack1.push(a);
        }
        res = 1;
        count = 0;
        while(!stack1.isEmpty()) {
            count++;
            int a = stack1.pop();
            res = res * a;
            if(res == 1) {
                ans = Math.max(ans, count);
            }
        }
        return ans;
    }
}
